// 给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。
// 输入：

// A: `[1,2,3,2,1]`
// B: `[3,2,1,4,7]`
// 输出：3
// 解释：长度最长的公共子数组是 [3, 2, 1] 。

// 子数组，其实是数组的连续子序列
// 用二维数组记录两个字符串的所有比较情况

// 五部曲

// 1. dp数组的含义，`dp[i][j]`, 以下标i-1的A，和下标j-1的B,最长重复的子数组
// 2. 确定递推公式
// ```js
// if(A[i-1] === B[j-1]) {
//     dp[i][j] = dp[i-1][j-1] + 1
// }
// ```
// 3. 初始化，`dp[0][0]`是没有意义的，所以`dp[0][0] = 0`
// 4. 确定遍历顺序，内外层遍历是A或B都行，从前往后
// 5. 举例

// 时间复杂度：O(n × m)，n 为A长度，m为B长度
// 空间复杂度：O(n × m)

function findLength(nums1, nums2) {
    let dp = new Array(nums1.length + 1).fill(0).map(_ => new Array(nums2.length + 1).fill(0))
    let result = 0
    for (let i = 1; i <= nums1.length; i++) {
        for (let j = 1; j <= nums2.length; j++) {
            // 这里的索引要注意，注意dp的定义
            if (nums1[i - 1] === nums2[j - 1]) {
                dp[i][j] = dp[i-1][j-1] + 1
            }
            result = Math.max(result, dp[i][j])
        }        
    }
    return result
}

// 思路2， 滚动数组
// `dp[i][j]`都是由`dp[i-1][j-1]`推导而来，压缩为一维数组，`dp[j]`都是由dp[j-1]推导
// 相当于把上一层的`dp[i-1][j]`拷贝到下一层`dp[i][j]`来用, 从后向前遍历，这样避免重复覆盖。
function findLength2(nums1, nums2) {
    let dp = new Array(nums2.length + 1).fill(0)
    let result = 0
    for (let i = 0; i <= nums1.length; i++) {
        for (let j = nums2.length; j > 0; j--) {
            // 注意这里的索引
            if (nums1[i-1] === nums2[j-1]) {
                dp[j] = dp[j - 1] + 1
            } else {
                dp[j] = 0
            }  
            result = Math.max(result, dp[j])     
        }
    }
    return result
}

let nums1 = [1,2,3,2,1]
let nums2 = [3,2,1,4,7]
console.log(findLength(nums1, nums2))
console.log(findLength2(nums1, nums2))